﻿#include"opt.h"

extern std::fstream pageTable_opt;

template < int N > static int find(PTE_x86< N > src, uint64_t id, bool mode)
// id:VPFN;mode:是否是查找,0:找空位,1:查找有无id
{
	if (mode == true)  // 查找是否匹配
	{
		for (int i = 0; i < N; i++)
            if (src.items[i].second & uint64_t(x86_PState::Present))
                return i;
            else
                return -1;
		return -1;
	}
	else if (mode == false)  // 查找有无空余
	{
		for (int i = 0; i < N; ++i)
		{
			if (src.items[i].first == 0)
				return i;
			else if (src.items[i].second ^ uint64_t(x86_PState::Accessed))
				return i;
			else
				src.items[i].second &=
				~uint64_t(x86_PState::Accessed);  // 第一次查找，清除访问标记
		}
		for (int i = 0; i < N; i++)
			if (src.items[i].second ^ uint64_t(x86_PState::Accessed))
				return i;
	}
	else return -1;
	return -1;
}
static int find(PTE_RISC& src, uint64_t id, bool mode)
// id:VPFN;mode:是否是查找,0:找空位,1:查找有无id
{
	if (mode == true)  // 查找是否匹配
	{
		for (int i = 0; i < 8; i++)
			if (src.items[i].first == id)
				return i;
		return -1;
	}
	else if (mode == false)  // 查找有无空余
	{
		for (int i = 0; i < 8; ++i)
		{
			if (src.items[i].first == 0)
				return i;
			else if (src.items[i].second ^ uint64_t(RISC_PState::Accessed))
				return i;
			else
				src.items[i].second &=
				~(uint64_t(RISC_PState::Accessed));  // 第一次查找，清除访问标记
		}
		for (int i = 0; i < 8; i++)
			if (src.items[i].second ^ uint64_t(RISC_PState::Accessed))
				return i;
	}
	else return -1;
	return -1;
}

void TLB_OPT_x86::l1i_search()
{
	int index = split[2].first & 0x07;
	int tlb_idx = find<8>(l1i_4k[index], split[2].first >> 3, true);
	if (tlb_idx == -1)
	{
		index = split[1].first & 0x03;
		tlb_idx = find<8>(l1i_2m[index], split[1].first, true);
		if (tlb_idx == -1)
		{
			index = split[0].first & 0x01;
			tlb_idx = find<8>(l1i_1g[index], split[0].first, true);
			if (tlb_idx == -1)
			{
				status = TLB_State::L2_SEARCH;
				return;
			}
		}
		else
		{
			tmp_var = l1i_2m[index].items[tlb_idx].second >> 12;
            status = TLB_State::CONCAT;
			valid[1] = true;
			valid[2] = valid[0] = false;
			return;
		}
	}
	else
	{
		tmp_var = l1i_4k[index].items[tlb_idx].second >> 12;
        status = TLB_State::CONCAT;
		valid[2] = true;
		valid[1] = valid[0] = false;
		return;
	}
}
void TLB_OPT_x86::l1d_search()
{
	int index = split[2].first & 0x0f;
	int tlb_idx = find<8>(l1d_4k[index], split[2].first >> 3, true);
	if (tlb_idx == -1)
	{
		index = split[1].first & 0x03;
		tlb_idx = find<8>(l1d_2m[index], (split[1].first) >> 2, true);
		if (tlb_idx == -1)
		{
			index = split[0].first & 0x01;
			tlb_idx = find<8>(l1d_1g[index], (split[0].first), true);
			if (tlb_idx == -1)
			{
				status = TLB_State::L2_SEARCH;
				return;
			}
			else
			{
				tmp_var = l1d_1g[index].items[tlb_idx].second >> 12;
				valid[0] = true;
				valid[1] = valid[2] = false;
				return;
			}
		}
		else
		{
			tmp_var = l1d_2m[index].items[tlb_idx].second >> 12;
			valid[1] = true;
			valid[2] = valid[0] = false;
			return;
		}
	}
	else
	{
		tmp_var = l1d_4k[index].items[tlb_idx].second >> 12;
		valid[2] = true;
		valid[1] = valid[0] = false;
		return;
	}
}
void TLB_OPT_x86::l2_search()
{
	int index = split[2].first & 0xff;
	int tlb_idx = find<8>(l2_4k[index], split[2].first >> 8, true);
	if (tlb_idx == -1)
	{
		index = split[1].first & 0x7f;
		tlb_idx = find<8>(l2_2m[index], (split[1].first) >> 7, true);
		if (tlb_idx == -1)
		{
			index = split[0].first & 0x3f;
			tlb_idx = find<8>(l2_1g[index], (split[0].first) >> 7, true);
			if (tlb_idx == -1)
			{
				status = TLB_State::CHK_LEV;
				return;
			}
			else
			{
				status = TLB_State::SWAP;
				swap_val = { index & 0x400,tlb_idx };
				tmp_var = l2_1g[index].items[tlb_idx].second >> 12;
				valid[0] = true;
				valid[1] = valid[2] = false;
				return;
			}
		}
		else
		{
			status = TLB_State::SWAP;
			swap_val = { index & 0x200,tlb_idx };
			tmp_var = l2_2m[index].items[tlb_idx].second >> 12;
			valid[1] = true;
			valid[2] = valid[0] = false;
			return;
		}
	}
	else
	{
		status = TLB_State::SWAP;
		swap_val = { index & 0x100,tlb_idx };
		tmp_var = l1d_4k[index].items[tlb_idx].second >> 12;
		valid[2] = true;
		valid[1] = valid[0] = false;
		return;
	}
}
void TLB_OPT_x86::swap()
{
	if (swap_val.first & 0x400)//1g swap
	{
		if (access ^ 0x08)
		{
			int index = split[0].first & 0x01;
			int tlb_idx = find<8>(l1d_1g[index], -1, false);
			std::swap(l1d_1g[index].items[tlb_idx], l2_1g[swap_val.first & 0x7f].items[swap_val.second]);
		}
		else
		{
			int index = split[0].first & 0x01;
			int tlb_idx = find<8>(l1i_1g[index], -1, false);
			std::swap(l1i_1g[index].items[tlb_idx], l2_1g[swap_val.first & 0x7f].items[swap_val.second]);
		}
	}
	else if (swap_val.first & 0x200)//2m swap
	{
		if (access ^ 0x08)
		{
			int index = split[1].first & 0x03;
			int tlb_idx = find<8>(l1d_2m[index], -1, false);
			std::swap(l1d_2m[index].items[tlb_idx],
				l2_2m[swap_val.first & 0x7f].items[swap_val.second]);
		}
		else
		{
			int index = split[1].first & 0x03;
			int tlb_idx = find<8>(l1i_2m[index], -1, false);
			std::swap(l1i_2m[index].items[tlb_idx],
				l2_2m[swap_val.first & 0x7f].items[swap_val.second]);
		}
	}
	else if (swap_val.first & 0x100)//4k swap
	{
		if (access ^ 0x08)
		{
			int tlb_idx = find<8>(l1d_4k[split[2].first & 0x07], -1, false);
			std::swap(l1d_4k[swap_val.first & 0x7f].items[tlb_idx],
				l2_4k[swap_val.first & 0x7f].items[swap_val.second]);
		}
		else
		{
			int tlb_idx = find<8>(l1i_4k[split[2].first & 0x07], -1, false);
			std::swap(l1i_4k[swap_val.first & 0x7f].items[tlb_idx],
				l2_4k[swap_val.first & 0x7f].items[swap_val.second]);
		}
	}
}
void TLB_OPT_x86::tick()
{
	int index = 0;
	int tlb_idx = 0;
	switch (status)
	{
		case TLB_State::IDLE:  // 空闲
			break;
		case TLB_State::SPLIT:  // 拆分
			valid[0] = valid[1] = valid[2] = false;
			split[0] = { address >> 30, address & 0x3fffffff };
			split[1] = { address >> 21, address & 0x1fffff };
			split[2] = { address >> 12, address & 0xfff };
			status = TLB_State::L1_SEARCH;
			p.total_clocks += 2;
			break;
		case TLB_State::L1_SEARCH:  // L1搜索
			if (access&4)        // 指令
				l1i_search();
			else
				l1d_search();
			p.total_clocks += 2;
			break;
		case TLB_State::L2_SEARCH:  // L2搜索
			l2_search();
			p.total_clocks += 2;
			break;
		case TLB_State::SWAP:  // 交换L1和L2
			swap();
			status = TLB_State::IDLE;
			p.total_clocks += 2;
			break;

		case TLB_State::CHK_LEV:// 确定要查询的层次
			if (address < RvBA)
			{
				status = TLB_State::ERROR;
				p.faults++;
			}
			else
			{
				uint64_t vpfn = address >> 12;
				if (vpfn <= 0x1ff)
				{ level = 3;opt_on = true; }
				else if (vpfn <= 0x3ffff) { level = 2;opt_on = true; }
				else if (vpfn <= 0x7ffffff) { level = 1;opt_on = true; }
				else { level = 0;opt_on = false; }
				status = TLB_State::PTE_IDX;
			}
			p.total_clocks += 2;
			break;
		case TLB_State::PTE_IDX:  // 确定PTE索引
            idx[0] = (split[0].first >> 9) & 0x1ff;
            idx[1] = split[0].first & 0x1ff;
            idx[2] = split[1].first & 0x1ff;
            idx[3] = split[2].first & 0x1ff;
			status = TLB_State::PTE_LDR;
			p.total_clocks += 2;
			break;
		case TLB_State::PTE_LDR:  // 加载PTE
            tmp_address += uint64_t(idx[level]) << 3;
			level++;
			pageTable_opt.read((char*)(&tmp_var), 8);
			status = TLB_State::PTE_VIF;
			p.total_clocks += 200;
			break;
		case TLB_State::PTE_VIF:  // 确定PTE有效性
			// 1. 检查有效性
			if (!(tmp_var & uint64_t(x86_PState::Present)))
				status = TLB_State::ERROR;
			// 2. 检查是否到达叶子页表项
			if ((level == 3) ||
				((level < 3) && (tmp_var & uint64_t(x86_PState::PageSize))))
			{  // 叶子项
				switch (level)
				{
					case 1:  // 1GiB
						index = split[0].first & 0x7f;
						tlb_idx =
							find<8>(l2_1g[index], split[0].first >> 7, false);
						l2_1g[index].items[tlb_idx] = { (split[0].first >> 7), tmp_var };
						break;
					case 2:  // 2MiB
						index = split[1].first & 0x7f;
						tlb_idx =
							find<8>(l2_2m[index], split[1].first >> 7, false);
						l2_2m[index].items[tlb_idx] = { (split[1].first >> 7), tmp_var };
						break;
					case 3:  // 4KiB
						index = split[2].first & 0xff;
						tlb_idx =
							find<8>(l2_4k[index], split[2].first >> 8, false);
						l2_4k[index].items[tlb_idx] = { (split[2].first >> 8), tmp_var };
						break;
				}
			}
			else
			{  // 非叶子项
				level++;
				status = TLB_State::PTE_LDR;
			}
			p.total_clocks += 2;
			break;
		case TLB_State::CONCAT://地址连接，已确保至少有一项有效
			if (valid[2])
			{
				address = split[2].second;
				address |= tmp_var << 12;
			}
			else if (valid[1])
			{
				address = split[1].second;
				address |= tmp_var << 21;
			}
			else
			{
				address = split[0].second;
				address |= tmp_var << 30;
			}
			status = TLB_State::IDLE;
			p.total_clocks += 2;
			break;
		case TLB_State::ERROR:
			status = TLB_State::IDLE;
			p.total_clocks += 2;
			break;
	}
}

void TLB_OPT_RISC::l1i_search()
{
	int index = split[2].first & 0x07;
	int tlb_idx = find(l1i_4k[index], split[2].first >> 3, true);
	if (tlb_idx == -1)
	{
		index = split[1].first & 0x03;
		tlb_idx = find(l1i_2m[index], split[1].first, true);
		if (tlb_idx == -1)
		{
			index = split[0].first & 0x01;
			tlb_idx = find(l1i_1g[index], split[0].first, true);
			if (tlb_idx == -1)
			{
				status = TLB_State::L2_SEARCH;
				return;
			}
			else
			{
				tmp_var = l1i_1g[index].items[tlb_idx].second >> 12;
				valid[0] = true;
				valid[1] = valid[2] = false;
				return;
			}
		}
		else
		{
			tmp_var = l1i_2m[index].items[tlb_idx].second >> 12;
			valid[1] = true;
			valid[2] = valid[0] = false;
			return;
		}
	}
	else
	{
		tmp_var = l1i_4k[index].items[tlb_idx].second >> 12;
		valid[2] = true;
		valid[1] = valid[0] = false;
		return;
	}
}
void TLB_OPT_RISC::l1d_search()
{
	int index = split[2].first & 0x0f;
	int tlb_idx = find(l1d_4k[index], split[2].first >> 3, true);
	if (tlb_idx == -1)
	{
		index = split[1].first & 0x03;
		tlb_idx = find(l1d_2m[index], (split[1].first) >> 2, true);
		if (tlb_idx == -1)
		{
			index = split[0].first & 0x01;
			tlb_idx = find(l1d_1g[index], (split[0].first), true);
			if (tlb_idx == -1)
			{
				status = TLB_State::L2_SEARCH;
				return;
			}
			else
			{
				tmp_var = l1d_1g[index].items[tlb_idx].second >> 12;
				valid[0] = true;
				valid[1] = valid[2] = false;
				return;
			}
		}
		else
		{
			tmp_var = l1d_2m[index].items[tlb_idx].second >> 12;
			valid[1] = true;
			valid[2] = valid[0] = false;
			return;
		}
	}
	else
	{
		tmp_var = l1d_4k[index].items[tlb_idx].second >> 12;
		valid[2] = true;
		valid[1] = valid[0] = false;
		return;
	}
}
void TLB_OPT_RISC::l2_search()
{
	int index = split[2].first & 0xff;
	int tlb_idx = find(l2_4k[index], split[2].first >> 8, true);
	if (tlb_idx == -1)
	{
		index = split[1].first & 0x7f;
		tlb_idx = find(l2_2m[index], (split[1].first) >> 7, true);
		if (tlb_idx == -1)
		{
			index = split[0].first & 0x3f;
			tlb_idx = find(l2_1g[index], (split[0].first) >> 7, true);
			if (tlb_idx == -1)
			{
				status = TLB_State::PTE_IDX;
				return;
			}
			else
			{
				status = TLB_State::SWAP;
				swap_val = { index & 0x400,tlb_idx };
				tmp_var = l2_1g[index].items[tlb_idx].second >> 12;
				valid[0] = true;
				valid[1] = valid[2] = false;
				return;
			}
		}
		else
		{
			status = TLB_State::SWAP;
			swap_val = { index & 0x200,tlb_idx };
			tmp_var = l2_2m[index].items[tlb_idx].second >> 12;
			valid[1] = true;
			valid[2] = valid[0] = false;
			return;
		}
	}
	else
	{
		status = TLB_State::SWAP;
		swap_val = { index & 0x100,tlb_idx };
		tmp_var = l1d_4k[index].items[tlb_idx].second >> 12;
		valid[2] = true;
		valid[1] = valid[0] = false;
		return;
	}
}
void TLB_OPT_RISC::swap()
{
	int index, tlb_idx;
	if (swap_val.first & 0x400)//1g swap
	{
		if (access ^ 0x08)
		{
			index = split[0].first & 0x01;
			tlb_idx = find(l1d_1g[index], -1, false);
			std::swap(l1d_1g[index].items[tlb_idx], l2_1g[swap_val.first & 0x7f].items[swap_val.second]);
		}
		else
		{
			index = split[0].first & 0x01;
			tlb_idx = find(l1i_1g[index], -1, false);
			std::swap(l1i_1g[index].items[tlb_idx], l2_1g[swap_val.first & 0x7f].items[swap_val.second]);
		}
	}
	else if (swap_val.first & 0x200)//2m swap
	{
		if (access ^ 0x08)
		{
			index = split[1].first & 0x03;
			tlb_idx = find(l1d_2m[index], -1, false);
			std::swap(l1d_2m[index].items[tlb_idx],
				l2_2m[swap_val.first & 0x7f].items[swap_val.second]);
		}
		else
		{
			index = split[1].first & 0x03;
			tlb_idx = find(l1i_2m[index], -1, false);
			std::swap(l1i_2m[index].items[tlb_idx],
				l2_2m[swap_val.first & 0x7f].items[swap_val.second]);
		}
	}
	else if (swap_val.first & 0x100)//4k swap
	{
		if (access ^ 0x08)
		{
			index = split[2].first & 0x0f;
			tlb_idx = find(l1d_4k[index], -1, false);
			std::swap(l1d_4k[index].items[tlb_idx],
				l2_4k[swap_val.first & 0x7f].items[swap_val.second]);
		}
		else
		{
			tlb_idx = find(l1i_4k[split[2].first & 0x07], -1, false);
			std::swap(l1i_4k[swap_val.first & 0x7f].items[tlb_idx],
				l2_4k[swap_val.first & 0x7f].items[swap_val.second]);
		}
	}
}
void TLB_OPT_RISC::tick()
{
	const uint64_t if_leaf = uint64_t(RISC_PState::Read) | uint64_t(RISC_PState::Write) | uint64_t(RISC_PState::Execute);
	int index = 0;
	int tlb_idx = 0;
	switch (status)
	{
		case TLB_State::IDLE:  // 空闲
			break;
		case TLB_State::SPLIT:  // 拆分
			valid[0] = valid[1] = valid[2] = false;
			split[0] = { address >> 30, address & 0x3fffffff };
			split[1] = { address >> 21, address & 0x1fffff };
			split[2] = { address >> 12, address & 0xfff };
			p.total_clocks += 2;
			break;
		case TLB_State::L1_SEARCH:  // L1搜索
			if (access == 1)        // 指令
				l1i_search();
			else
				l1d_search();
			p.total_clocks += 2;
			break;
		case TLB_State::L2_SEARCH:  // L2搜索
			l2_search();
			p.total_clocks += 2;
			break;
		case TLB_State::SWAP:  // 交换L1和L2
			swap();
			status = TLB_State::IDLE;
			p.total_clocks += 2;
			break;
		case TLB_State::PTE_IDX:  // 确定PTE索引
			level = 0;
			idx[0] = (split[2].first >> 27) & 0x1ff;
			idx[1] = (split[2].first >> 18) & 0x1ff;
			idx[2] = (split[2].first >> 9) & 0x1ff;
			idx[3] = split[2].first & 0x1ff;
			status = TLB_State::PTE_LDR;
			p.total_clocks += 2;
			break;
		case TLB_State::PTE_LDR:  // 加载PTE
			tmp_address += idx[level] << 3;
			level++;
			pageTable_opt.read((char*)(&tmp_var), 8);
			status = TLB_State::PTE_VIF;
			p.total_clocks += 200;
			break;
		case TLB_State::PTE_VIF:  // 确定PTE有效性
			// 1. 检查有效性
			if (!(tmp_var & uint64_t(RISC_PState::Valid)))
				status = TLB_State::ERROR;
			// 2. 检查是否到达叶子页表项
			if ((level == 3) ||
				((level < 3) && (tmp_var & if_leaf)))
			{  // 叶子项
				switch (level)
				{
					case 1:  // 1GiB
						index = split[0].first & 0x7f;
						tlb_idx =
							find(l2_1g[index], split[0].first >> 7, false);
						l2_1g[index].items[tlb_idx] = { (split[0].first >> 7), tmp_var };
						break;
					case 2:  // 2MiB
						index = split[1].first & 0x7f;
						tlb_idx =
							find(l2_2m[index], split[1].first >> 7, false);
						l2_2m[index].items[tlb_idx] = { (split[1].first >> 7), tmp_var };
						break;
					case 3:  // 4KiB
						index = split[2].first & 0xff;
						tlb_idx =
							find(l2_4k[index], split[2].first >> 8, false);
						l2_4k[index].items[tlb_idx] = { (split[2].first >> 8), tmp_var };
						break;
				}
			}
			else
			{  // 非叶子项
				level++;
				status = TLB_State::PTE_LDR;
			}
			p.total_clocks += 2;
			break;
		case TLB_State::CONCAT://地址连接，已确保至少有一项有效
			if (valid[2])
			{
				address = split[2].second;
				address |= tmp_var << 12;
			}
			else if (valid[1])
			{
				address = split[1].second;
				address |= tmp_var << 21;
			}
			else
			{
				address = split[0].second;
				address |= tmp_var << 30;
			}
			status = TLB_State::IDLE;
			p.total_clocks += 2;
			break;
		case TLB_State::ERROR:
			status = TLB_State::IDLE;
			p.faults++;
			p.total_clocks += 2;
			break;
	}
}